package week_10;

public class NumArrayBinaryIndexedTree_my {
    int[] c;
    int[] nums;

    public NumArrayBinaryIndexedTree_my(int[] nums) {
        // 树状数组的初始化
        this.nums = nums;
        this.c = new int[nums.length + 1];
        c[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            c[i] = nums[i - 1];
            System.out.println(i + "--------lowbit:" + lowbit(i));
            for (int j = i - 1; j > i - (i & -i); j--) {
                System.out.println(j);
                c[i] += nums[j - 1];
            }
        }
    }

    public void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        index += 1;
        for (; index <= nums.length; index += index & -index) {
            c[index] += diff;
        }
    }

    public int sumRange(int left, int right) {
        // c[r]-c[l-1]
        return query(right) - query(left - 1);
    }

    public int query(int x) {
        int ans = 0;
        x += 1;
        for (; x > 0; x -= x & -x) ans += c[x];
        return ans;
    }

    public int lowbit(int x) {
        return x & -x;
    }

    public static void main(String[] args) {
//["NumArray","update","update","update","sumRange","update","sumRange","update","sumRange","sumRange","update"]
//[update[[7,2,7,2,0]],[4,6],[0,2],[0,9],[4,4],[3,8],[0,4],[4,1],[0,3],[0,4],[0,4]]
        int[] nums = {7, 2, 7, 2, 0};
        NumArrayBinaryIndexedTree_my numArray = new NumArrayBinaryIndexedTree_my(nums);
        numArray.update(4, 6);
        numArray.update(0, 2);
        numArray.update(0, 9);

        numArray.update(1, 2);
        int ans2 = numArray.sumRange(0, 2);
        System.out.println(ans2);
    }
}
